# lintcode: (79) Longest Common Substring
# Given two strings, find the longest common substring.
# Return the length of it.

# Example
# Given A="ABCD", B="CBCE", return 2.
# Note
# The characters in substring should occur continuously in original string.
# This is different with subsequence.
# 思路 两个指针移动
def longestCommonSubstring(A, B):
	if len(A) == 0 or len(B) == 0: return 0
	lcs = 0	# 存储最长子串的长度
	for i in range(0,len(A)):
		for j in range(0,len(B)):
			lcs_temp = 0 
			while i+lcs_temp < len(A) and j + lcs_temp < len(B) and A[i+lcs_temp]==B[j+lcs_temp]:
				lcs_temp = lcs_temp+1
			if lcs_temp > lcs:
				lcs = lcs_temp
	return lcs

size = longestCommonSubstring('sdfjksail','ksaila')
print(size)

# 算法复杂度分析
#双重 for 循环，最坏时间复杂度约为 O(mn * lcs) 